package com.leetcode.algorithm.y22.m06;

/**
 * 198. 打家劫舍
 * 
 * https://leetcode.cn/problems/house-robber/
 * 
 * @author jie.deng
 *
 */
class Question0198Solution01 {

	public int rob(int[] nums) {
		int len = nums.length;

		// DP状态定义
		// dp[i]表示
		int[][] dp = new int[len][2];

		// DP状态初始化
		// 不闯入i号房屋能够偷窃到的最高金额
		// 闯入i号房屋能够偷窃到的最高金额
		dp[0][0] = 0;
		dp[0][1] = nums[0];

		// 状态转移方程：
		for (int i = 1; i < len; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
			dp[i][1] = dp[i - 1][0] + nums[i];
		}

		return Math.max(dp[len - 1][0], dp[len - 1][1]);
	}

}